package com.algrithom.tree.bst;

import java.util.Arrays;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 98. 验证二叉搜索树
 */
public class Solution3 {
    
    public static void main(String[] args){
        Integer[] list = new Integer[]{5,3,6,2,4,null,null};
        TreeNode<Integer> root = TreeOperUtil.createBstTree(Arrays.asList(list),0,list.length - 1);
        Solution3 solution3 = new Solution3();
        System.out.println(solution3.isValidBST(root));
    }
    
    public boolean isValidBST(TreeNode<Integer> root){
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    
    public boolean isValidBST(TreeNode<Integer> node,long lower,long upper){
        if (node == null) {
            return true;
        }
        if (node.getValue() <= lower || node.getValue() >= upper) {
            return false;
        }
        return isValidBST(node.getLeftChild(),lower,node.getValue()) && isValidBST(node.getRightChild(),node.getValue(),upper);
    }
}
